package com.gxc.graph;

import java.util.*;

/**
 * 宽度优先
 */
public class BreadthFirst {

    public static void main(String[] args) {
        Graph graph = createGraph();

        breadth_First(graph);
    }

    /**
     * 宽度优先遍历
     * @param graph
     */
    private static void breadth_First(Graph graph) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(graph.nodes.get(1));
        //确保已经遍历过的node不再处理
        Set<Node> set = new HashSet<>();
        set.add(graph.nodes.get(1));

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.value + " ");
            for (Node next : node.nexts) {
                if (!set.contains(next)) {
                    set.add(next);
                    queue.add(next);
                }
            }
        }
    }

    //创建图
    public static Graph createGraph() {
        HashMap<Integer, Node> map = new HashMap<>();
        HashSet<Edge> edges = new HashSet<>();
        Node node1 = new Node(1, 0, 3);
        Node node2 = new Node(2, 1, 2);
        Node node3 = new Node(3, 1, 1);
        Node node4 = new Node(4, 1, 0);
        Node node5 = new Node(5, 1, 0);
        Node node6 = new Node(6, 1, 0);
        Node node7 = new Node(7, 1, 0);

        map.put(1, node1);
        map.put(2, node2);
        map.put(3, node3);
        map.put(4, node4);
        map.put(5, node5);
        map.put(6, node6);
        map.put(7, node7);

        ArrayList<Node> node1next = new ArrayList<>();
        node1next.add(node2);
        node1next.add(node3);
        node1next.add(node4);
        node1.nexts = node1next;

        ArrayList<Node> node2next = new ArrayList<>();
        node2next.add(node5);
        node2next.add(node6);
        node2.nexts = node2next;

        ArrayList<Node> node3next = new ArrayList<>();
        node3next.add(node7);
        node3.nexts = node3next;

        Edge edge1 = new Edge(1, node1, node2);
        Edge edge2 = new Edge(2, node1, node3);
        Edge edge3 = new Edge(3, node1, node4);
        Edge edge4 = new Edge(4, node2, node5);
        Edge edge5 = new Edge(5, node2, node6);
        Edge edge6 = new Edge(6, node3, node7);

        ArrayList<Edge> node1edgs = new ArrayList<>();
        node1edgs.add(edge1);
        node1edgs.add(edge2);
        node1edgs.add(edge3);
        node1.edges = node1edgs;

        ArrayList<Edge> node2edgs = new ArrayList<>();
        node2edgs.add(edge4);
        node2edgs.add(edge5);
        node2.edges = node2edgs;

        ArrayList<Edge> node3edgs = new ArrayList<>();
        node3edgs.add(edge6);
        node3.edges = node3edgs;

        edges.add(edge1);
        edges.add(edge2);
        edges.add(edge3);
        edges.add(edge4);
        edges.add(edge5);
        edges.add(edge6);
        Graph graph = new Graph(map, edges);
        return graph;
    }
}
